import java.util.HashMap;

/*
 * @lc app=leetcode.cn id=76 lang=java
 *
 * [76] 最小覆盖子串
 */

// @lc code=start
class Solution {
    public String minWindow(String s, String t) {
        HashMap<Character,Integer> map=new HashMap<>();
        for(char ch:t.toCharArray()){//统计t每个字符出现个数
            map.put(ch, map.getOrDefault(ch, 0)+1);
        }
        int left=0;//左指针
        int right=0;//右指针
        int statIdx=0;//记录窗口起始位置
        int windowLen=Integer.MAX_VALUE;//记录窗口大小

        while(right<s.length()){
            char rc=s.charAt(right);
            if(map.containsKey(rc)){
                map.put(rc, map.get(rc)-1);
            }
            right++;

            while(check(map)){//考虑是否需要收缩
               //首先判断当前子串是否是最小的合法子串
                if(right-left<windowLen){
                    statIdx=left;
                    windowLen=right-left;
                }
                //更新map
                if(map.containsKey(s.charAt(left))){
                    map.put(s.charAt(left), map.get(s.charAt(left))+1);
                }
                //左边界右移
                left++;
            }
        }
        return windowLen==Integer.MAX_VALUE? "":s.substring(statIdx, statIdx+windowLen);
    }

    /*判断是否全部覆盖t */
    private boolean check(HashMap<Character, Integer> map) {
        for(int value:map.values()){
            if(value>0){
                return false;
            }
        }
        return true;
    }
}
// @lc code=end

